Toroidal graph

In mathematics, a graph G is toroidal if it can be embedded on the torus. In other words, the graph's vertices can be placed on a torus such that no edges cross. Usually, it is assumed that G is also non-planar.

Contents

Examples

The Heawood graph, the complete graph K7 (and hence K5 and K6), the Petersen graph (and hence the complete bipartite graph K3,3, since the Petersen graph contains a subdivision of it), the Blanuša snarks,[1] and all Möbius ladders are toroidal. More generally, any graph with crossing number 1 is toroidal. Some graphs with greater crossing numbers are also toroidal: the Möbius–Kantor graph, for example, has crossing number 4 and is toroidal.[2]

Properties

Any toroidal graph has chromatic number at most 7.[3] The complete graph K7 provides an example of toroidal graph with chromatic number 7.[4]

Any triangle-free toroidal graph has chromatic number at most 4.[5]

By a result analogous to Fáry's theorem, any toroidal graph may be drawn with straight edges in a rectangle with periodic boundary conditions.[6] Furthermore, the analogue of Tutte's spring theorem applies in this case.[7] Toroidal graphs also have book embeddings with at most 7 pages.[8]

See also

Notes

  1. ^ Orbanić et al. (2004).
  2. ^ Marušič & Pisanski (2000).
  3. ^ Heawood (1890).
  4. ^ Chartrand & Zhang (2008).
  5. ^ Kronk & White (1972).
  6. ^ Kocay, Neilson & Szypowski (2001).
  7. ^ Gortler, Gotsman & Thurston (2006).
  8. ^ Endo (1997).

References